package hashTable

import "math"

/*
时间算法复杂度：O(n+C) c是2*10^4 即nums[i]的范围
空间算法复杂度:O(n)
*/

func findKthLargest(nums []int, k int) int {
	m := make(map[int]int)
	maxVal := math.MinInt32
	for _, v := range nums {
		m[v]++
		if maxVal < v {
			maxVal = v
		}
	}

	for i := maxVal; i >= int(math.Pow(10, -4)) && k > 0; i-- {
		if count, ok := m[i]; ok {
			if k <= count {
				return i
			}
			k -= count
		}
	}
	return math.MinInt32
}

func findKthLargest1(nums []int, k int) int {
	base := int(math.Pow(10, 4))
	bucket := make([]int, 2*base+1)
	for _, v := range nums {
		bucket[v+base]++
	}

	for i := len(bucket) - 1; i >= 0 && k > 0; i-- {
		if k <= bucket[i] {
			return i - base
		}
		k -= bucket[i]
	}
	return math.MinInt32
}
